package 数组中重复的数字;

public class Solution
{
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[], int length, int[] duplication)
    {
        //判断输入
        if (numbers == null || numbers.length < 2)
            return false;
        for (int i = 0; i < length; i++)
        {
            if (numbers[i] < 0 || numbers[i] > length - 1)
                return false;
        }
        for (int i = 0; i < length; i++)
        {
            while (numbers[i] != i)
            {
                if (numbers[i] == numbers[numbers[i]])
                {
                    duplication[0] = numbers[i];
                    return true;
                }
                //交换位置
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return false;
    }

    public static void main(String[] args)
    {
        Solution solution = new Solution();
        int[] test = {2, 3, 1, 0, 2, 5, 3};
        int[] dup = new int[1];
        solution.duplicate(test, test.length, dup);
    }
    //不修改数组找出重复的所有数字,长度为n+1的数组中，所有数字的范围都在1~n之间
    //可以直接用一个int[]
    //二分查找法

}
